# alg.py

def longest_substring(s: str, k: int) -> int:
    """
    分治算法：返回满足每个字符至少出现k次的最长子串长度
    """
    if len(s) < k:
        return 0

    for c in set(s):
        if s.count(c) < k:
            return max(longest_substring(t, k) for t in s.split(c))
    
    return len(s)


